{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #IP to CIDR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: ipToCIDR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #IP 到 CIDR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>IP地址</strong> 是一个格式化的 32位 无符号整数，每组 8位 被打印为一个十进制数字和，点字符&nbsp;<code>'.'</code>&nbsp;起到了分组的作用。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，二进制数 <code>00001111 10001000 11111111 01101011</code>&nbsp;( 为清晰起见增加了空格)被格式化为IP地址将是 <code>“15.136.255.107”</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>CIDR块</strong> 是一种用来表示一组特定IP地址的格式。字符串形式，由基础IP地址、斜杠和前缀长度 <code>k</code> 组成。它所覆盖的地址是所有IP地址的 <strong>前 <code>k</code> 位</strong> 与基础IP地址相同的IP地址。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如， <code>“123.45.67.89/20”</code> 是一个前缀长度为 <code>20</code> 的&nbsp;<strong>CIDR块</strong>。任何二进制表示形式匹配 <code>01111011 00101101 0100xxxx xxxxxxxx</code> 的IP地址，其中 <code>x</code> 可以是 <code>0</code> 或 <code>1</code> ，都在CIDR块覆盖的集合中。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个起始IP地址&nbsp;<code>ip</code>&nbsp;和我们需要覆盖的IP地址数量 <code>n</code> 。你的目标是使用 <strong>尽可能少的CIDR块</strong> 来&nbsp;<strong>覆盖范围&nbsp;<code>[ip, ip + n - 1]</code>&nbsp;内的所有IP地址</strong>&nbsp;。不应该覆盖范围之外的其他IP地址。</p>\n",
    "\n",
    "<p>返回 <em>包含IP地址范围的 <strong>CIDR块</strong> 的 <strong>最短</strong> 列表。如果有多个答案，返回其中 <strong>任何</strong> 一个&nbsp;</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>ip = \"255.0.0.7\", n = 10\n",
    "<strong>输出：</strong>[\"255.0.0.7/32\",\"255.0.0.8/29\",\"255.0.0.16/32\"]\n",
    "<strong>解释：\n",
    "</strong>需要覆盖的IP地址有:\n",
    "- 255.0.0.7 -&gt; 11111111 00000000 00000000 00000111\n",
    "- 255.0.0.8 -&gt; 11111111 00000000 00000000 00001000\n",
    "- 255.0.0.9 -&gt; 11111111 00000000 00000000 00001001\n",
    "- 255.0.0.10 -&gt; 11111111 00000000 00000000 00001010\n",
    "- 255.0.0.11 -&gt; 11111111 00000000 00000000 00001011\n",
    "- 255.0.0.12 -&gt; 11111111 00000000 00000000 00001100\n",
    "- 255.0.0.13 -&gt; 11111111 00000000 00000000 00001101\n",
    "- 255.0.0.14 -&gt; 11111111 00000000 00000000 00001110\n",
    "- 255.0.0.15 -&gt; 11111111 00000000 00000000 00001111\n",
    "- 255.0.0.16 -&gt; 11111111 00000000 00000000 00010000\n",
    "CIDR区块“255.0.0.7/32”包含第一个地址。\n",
    "CIDR区块255.0.0.8/29包含中间的8个地址(二进制格式为11111111 00000000 00000000 00001xxx)。\n",
    "CIDR区块“255.0.0.16/32”包含最后一个地址。\n",
    "请注意，虽然CIDR区块“255.0.0.0/28”覆盖了所有的地址，但它也包括范围之外的地址，所以我们不能使用它。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>ip = \"117.145.102.62\", n = 8\n",
    "<b>输出：</b>[\"117.145.102.62/31\",\"117.145.102.64/30\",\"117.145.102.68/31\"]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>7 &lt;= ip.length &lt;= 15</code></li>\n",
    "\t<li><code>ip</code>&nbsp;是一个有效的&nbsp;<strong>IPv4</strong>&nbsp;，形式为&nbsp;<code>\"a.b.c.d\"</code>&nbsp;，其中&nbsp;<code>a</code>,&nbsp;<code>b</code>,&nbsp;<code>c</code>,&nbsp;&nbsp;<code>d</code>&nbsp;是&nbsp;<code>[0, 255]</code>&nbsp;范围内的整数</li>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li>每个隐含地址&nbsp;<code>ip + x</code>&nbsp;(&nbsp;<code>x &lt; n</code>) 都是有效的 IPv4 地址</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ip-to-cidr](https://leetcode.cn/problems/ip-to-cidr/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ip-to-cidr](https://leetcode.cn/problems/ip-to-cidr/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"255.0.0.7\"\\n10', '\"117.145.102.62\"\\n8']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ipToCIDR(self, ip: str, n: int) -> List[str]:\n",
    "        def ip_to_int(ip):\n",
    "            ans = 0\n",
    "            for x in ip.split('.'):\n",
    "                ans = ans * 256 + int(x)\n",
    "            return ans\n",
    "        \n",
    "        def int_to_ip(val):\n",
    "            return '.'.join(str((val >> i) % 256) for i in (24, 16, 8, 0))\n",
    "        \n",
    "        ip_int = ip_to_int(ip)\n",
    "        result = []\n",
    "        while n:\n",
    "            mask = max(33 - (ip_int & -ip_int).bit_length(), 33 - n.bit_length())\n",
    "            if ip_int == 0:\n",
    "                mask = 33 - n.bit_length()\n",
    "            result.append(int_to_ip(ip_int) + '/' + str(mask))\n",
    "            ip_int += 1 << (32 - mask)\n",
    "            n -= 1 << (32 - mask)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Start with the initial ip address and repeat until we've covered ip + n - 1:\n",
    "        Since we want the smallest number of CIDR blocks, we want to use as large a block as possible.\n",
    "        Find the number of trailing 0s in the current ip's binary representation - let this be k.\n",
    "        The current block can cover 2^k ip addresses (with the first one being the current ip).\n",
    "        If this exceeds n, decrement k until it doesn't.\n",
    "        Add the current block to the result and move to the next ip address.\n",
    "    For easier bit manipulation, we can convert an ip address to an integer whose binary representation represents the ip address.\n",
    "    Time complexity: O(n). Space complexity: O(1) (neglecting the output list).\n",
    "    '''\n",
    "    def ipToCIDR(self, ip: str, n: int) -> List[str]:\n",
    "        # convert an ip address to an integer whose binary representation represents the ip address\n",
    "        def ipToInt(ip: str) -> int:\n",
    "            res = 0\n",
    "            for part in ip.split('.'):\n",
    "                num = int(part)\n",
    "                res = res * 256 + num\n",
    "            return res\n",
    "\n",
    "        # convert an integer whose binary representation represents an ip address to the ip address\n",
    "        def intToIp(num: int) -> str:\n",
    "            res = []\n",
    "            for _ in range(4):\n",
    "                res.append(str(num % 256))\n",
    "                num //= 256\n",
    "            return '.'.join(res[::-1])\n",
    "\n",
    "        # count the number of trailing 0s in the binary representation of an integer\n",
    "        def countTrailingZeros(num: int) -> int:\n",
    "            if num == 0: # special case\n",
    "                return 32\n",
    "\n",
    "            res = 0\n",
    "            while num & 1 == 0:\n",
    "                res += 1\n",
    "                num >>= 1\n",
    "            return res\n",
    "\n",
    "        res = []\n",
    "        ipInt = ipToInt(ip)\n",
    "        while n > 0:\n",
    "            k = countTrailingZeros(ipInt)\n",
    "            while 2 ** k > n:\n",
    "                k -= 1\n",
    "            \n",
    "            # the current CIDR block masks the last k bits of ipInt and covers 2^k ip addresses\n",
    "            res.append(intToIp(ipInt) + '/' + str(32 - k))\n",
    "            n -= 2 ** k\n",
    "            ipInt += 2 ** k\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ipToCIDR(self, ip: str, n: int) -> List[str]:\n",
    "        def ip_to_int(ip):\n",
    "            ans = 0\n",
    "            for x in ip.split('.'):\n",
    "                ans = 256 * ans + int(x)\n",
    "            # return ans\n",
    "            octets = [int(octet) for octet in ip.split('.')]\n",
    "            return (octets[0] << 24) + (octets[1] << 16) + (octets[2] << 8) + octets[3]\n",
    "        \n",
    "        def int_to_ip(x):\n",
    "            return '.'.join(str((x >> i) % 256) for i in (24, 16, 8, 0))\n",
    "        \n",
    "        start = ip_to_int(ip)\n",
    "        print(bin(start))\n",
    "        res = []\n",
    "        while n:\n",
    "            low_bit = (start & -start)\n",
    "            mask = max(33 - low_bit.bit_length(), 33 - n.bit_length())\n",
    "            if low_bit == 0 and n == 1:\n",
    "                mask = 32\n",
    "            elif low_bit == 0:\n",
    "                mask = 33 - n.bit_length()\n",
    "            res.append(int_to_ip(start) + '/' + str(mask))\n",
    "            start += 1 << (32 - mask)\n",
    "            n -= 1 << (32 - mask)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ipToCIDR(self, ip: str, n: int) -> List[str]:\n",
    "        ips = ip.split(\".\")\n",
    "        ipn = 0\n",
    "        for part in ips:\n",
    "            ipn = ((ipn) << 8) + int(part)\n",
    "\n",
    "        ret = []\n",
    "        curr = ipn\n",
    "        #print(bin(curr))\n",
    "        while n > 0:\n",
    "            mask = max(33 - (curr & -curr).bit_length(),\n",
    "                       33 - n.bit_length())\n",
    "            if curr == 0:\n",
    "                mask = 33 - n.bit_length()\n",
    "            ret.append([curr, mask])\n",
    "            #print(mask, n.bit_length(), n, curr & -curr, (curr & -curr).bit_length())\n",
    "            curr += 1 << (32 - mask)\n",
    "            n -= 1 << (32 - mask)\n",
    "\n",
    "        def to_ip(n):\n",
    "            ret = []\n",
    "            for i in range(4):\n",
    "                curr = str((n >> i * 8) & 255)\n",
    "                #print(bin(n), (n >> i) & 255)\n",
    "                ret.append(curr)\n",
    "            return \".\".join(ret[::-1])\n",
    "\n",
    "        return [to_ip(x[0]) + \"/\" + str(x[1]) for x in ret]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "1P3A:\n",
    "https://www.1point3acres.com/bbs/thread-1014490-1-1.html\n",
    "https://www.1point3acres.com/bbs/thread-828501-1-1.html\n",
    "https://www.1point3acres.com/bbs/thread-1014067-1-1.html\n",
    "https://www.1point3acres.com/bbs/thread-1012995-1-1.html\n",
    "https://www.1point3acres.com/bbs/thread-1006992-1-1.html\n",
    "https://www.1point3acres.com/bbs/thread-1003442-1-1.html\n",
    "https://www.1point3acres.com/bbs/thread-940767-1-1.html\n",
    "https://www.1point3acres.com/bbs/thread-933131-1-1.html\n",
    "\n",
    "LC:\n",
    "https://leetcode.cn/problems/ip-to-cidr\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Start with the initial ip address and repeat until we've covered ip + n - 1:\n",
    "        Since we want the smallest number of CIDR blocks, we want to use as large a block as possible.\n",
    "        Find the number of trailing 0s in the current ip's binary representation - let this be k.\n",
    "        The current block can cover 2^k ip addresses (with the first one being the current ip).\n",
    "        If this exceeds n, decrement k until it doesn't.\n",
    "        Add the current block to the result and move to the next ip address.\n",
    "    For easier bit manipulation, we can convert an ip address to an integer whose binary representation represents the ip address.\n",
    "    Time complexity: O(n). Space complexity: O(1) (neglecting the output list).\n",
    "    '''\n",
    "    def ipToCIDR(self, ip: str, n: int) -> list[str]:\n",
    "        # convert an ip address to an integer whose binary representation represents the ip address\n",
    "        def ipToInt(ip: str) -> int:\n",
    "            res = 0\n",
    "            for part in ip.split('.'):\n",
    "                num = int(part)\n",
    "                res = res * 256 + num\n",
    "            return res\n",
    "\n",
    "        # convert an integer whose binary representation represents an ip address to the ip address\n",
    "        def intToIp(num: int) -> str:\n",
    "            res = []\n",
    "            for _ in range(4):\n",
    "                res.append(str(num % 256))\n",
    "                num //= 256\n",
    "            return '.'.join(res[::-1])\n",
    "\n",
    "        # count the number of trailing 0s in the binary representation of an integer\n",
    "        def countTrailingZeros(num: int) -> int:\n",
    "            if num == 0: # special case\n",
    "                return 32\n",
    "\n",
    "            res = 0\n",
    "            while num & 1 == 0:\n",
    "                res += 1\n",
    "                num >>= 1\n",
    "            return res\n",
    "\n",
    "        res = []\n",
    "        ipInt = ipToInt(ip)\n",
    "        while n > 0:\n",
    "            k = countTrailingZeros(ipInt)\n",
    "            while 2 ** k > n:\n",
    "                k -= 1\n",
    "            \n",
    "            # the current CIDR block masks the last k bits of ipInt and covers 2^k ip addresses\n",
    "            res.append(intToIp(ipInt) + '/' + str(32 - k))\n",
    "            n -= 2 ** k\n",
    "            ipInt += 2 ** k\n",
    "        return res\n",
    "    \n",
    "'''\n",
    "Given a list of rules:\n",
    "[\n",
    "    (\"ALLOW\", \"1.2.3.4/32\"),\n",
    "    (\"DENY\", \"5.6.7.8/30\"),\n",
    "    ...\n",
    "]\n",
    "Determines whether an ip address is allowed or denied.\n",
    "\n",
    "Assumptions:\n",
    "    There is no contradicting rules (e.g. ALLOW and DENY rules that both apply to the ip address).\n",
    "    It's guaranteed that the ip address can match a rule.\n",
    "\n",
    "We can convert any ip address to an integer whose binary representation represents the ip address.\n",
    "For checking whether an ip address is contained in a CIDR block, \n",
    "    we can convert both addresses to integers and check whether the first k binary bits are the same by shifting.\n",
    "Time complexity: O(n). Space complexity: O(1).\n",
    "'''\n",
    "\n",
    "# convert an ip address to an integer whose binary representation represents the ip address\n",
    "def ipToInt(ip: str) -> int:\n",
    "    res = 0\n",
    "    for part in ip.split('.'):\n",
    "        num = int(part)\n",
    "        res = res * 256 + num\n",
    "    return res\n",
    "\n",
    "def isIPAllowed(rules: list[tuple[str, str]], ip: str) -> bool:\n",
    "    ipInt = ipToInt(ip)\n",
    "    for status, cidr in rules:\n",
    "        cidrIP, cidrLen = cidr.split('/')\n",
    "        cidrIPInt = ipToInt(cidrIP)\n",
    "        if ipInt >> (32 - int(cidrLen)) == cidrIPInt >> (32 - int(cidrLen)):\n",
    "            return status == 'ALLOW'\n",
    "\n",
    "'''\n",
    "What if there are many ip addresses to check?\n",
    "\n",
    "Store the rules in a hash table, with the meaningful part of the ip address as the key and the status as the value.\n",
    "For each ip address, apply each of the 31 possible masks to it and check whether the resulting ip address is in the hash table.\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def ip2num(self, ip):\n",
    "        ip_chunks = ip.split('.')\n",
    "        res = 0\n",
    "        for ip_chunk in ip_chunks:\n",
    "            res = res * 256 + int(ip_chunk)\n",
    "        return res\n",
    "    \n",
    "    def num2ip(self, ip_num):\n",
    "        return str((ip_num >> 24) % 256) + '.' + str((ip_num >> 16) % 256) + '.' + str((ip_num >> 8) % 256) + '.' + str(ip_num % 256)\n",
    "    \n",
    "    def find_rightmost_one(self, num):\n",
    "        return int(math.log2(num))\n",
    "    \n",
    "    def ipToCIDR(self, ip: str, n: int) -> List[str]:\n",
    "        \n",
    "        remain_n = n\n",
    "        res = []\n",
    "        ip_num = self.ip2num(ip)\n",
    "\n",
    "        while remain_n > 0:\n",
    "            right_one = ip_num & (-ip_num)\n",
    "            n_mask_left_one = 32 - (self.find_rightmost_one(right_one) if right_one > 0 else 0)\n",
    "            n_cover_remain = 32 - math.floor(math.log2(remain_n)) if remain_n > 0 else 32\n",
    "            if (right_one == 0):\n",
    "                mask = n_cover_remain\n",
    "            else:\n",
    "                mask = max(n_mask_left_one, n_cover_remain)\n",
    "            res.append(self.num2ip(ip_num) + '/' + str(mask))\n",
    "            ip_num += 1 << (32 - mask)\n",
    "            remain_n -= 1 << (32 - mask)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import log2\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def ipToCIDR(self, ip: str, n: int) -> List[str]:\n",
    "\n",
    "\n",
    "\n",
    "        def ip_to_int(ip):\n",
    "\n",
    "            num = 0\n",
    "\n",
    "            for x in ip.split('.'):\n",
    "\n",
    "                num *= 256\n",
    "\n",
    "                num += int(x)\n",
    "\n",
    "            return num\n",
    "\n",
    "\n",
    "\n",
    "        def int_to_ip(num):\n",
    "\n",
    "            lst = []\n",
    "\n",
    "            for _ in range(4):\n",
    "\n",
    "                num, r = divmod(num, 256)\n",
    "\n",
    "                lst.append(str(r))\n",
    "\n",
    "            return '.'.join(lst[::-1])\n",
    "\n",
    "\n",
    "\n",
    "        def low_bit(num):\n",
    "\n",
    "            return num & (-num)\n",
    "\n",
    "\n",
    "\n",
    "        res = []\n",
    "\n",
    "        num = ip_to_int(ip)\n",
    "\n",
    "        while n:\n",
    "\n",
    "            count = low_bit(num) or 1024\n",
    "\n",
    "            while count > n:\n",
    "\n",
    "                count >>= 1\n",
    "\n",
    "            res.append(int_to_ip(num) + '/' + str(32 - int(log2(count))))\n",
    "\n",
    "            num += count\n",
    "\n",
    "            n -= count\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ipToCIDR(self, ip: str, n: int) -> List[str]:\n",
    "        def b(x, bt):\n",
    "            s = \"\"\n",
    "            x = x - (x & (bt - 1))\n",
    "            for i in range(4):\n",
    "                s = str(x % 256) + '.' + s\n",
    "                x >>= 8\n",
    "            return s[:-1] + \"/\" + str(35 - len(bin(bt)))\n",
    "        \n",
    "        res, ans = 0, []\n",
    "        for i in ip.split(\".\"):\n",
    "            res = int(i) + res * 256\n",
    "        end = res + n\n",
    "        if res == 0:\n",
    "            res += 1 << (len(bin(n))-3)\n",
    "            ans.append(f\"0.0.0.0/{35 - len(bin(n))}\")\n",
    "        while res + (iobit := res & (-res)) <= end:\n",
    "            ans.append(b(res, iobit))\n",
    "            res += iobit\n",
    "        while res < end:\n",
    "            if res + iobit <= end:\n",
    "                ans.append(b(res, iobit))\n",
    "                res += iobit\n",
    "            iobit >>= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Start with the initial ip address and repeat until we've covered ip + n - 1:\n",
    "        Since we want the smallest number of CIDR blocks, we want to use as large a block as possible.\n",
    "        Find the number of trailing 0s in the current ip's binary representation - let this be k.\n",
    "        The current block can cover 2^k ip addresses (with the first one being the current ip).\n",
    "        If this exceeds n, decrement k until it doesn't.\n",
    "        Add the current block to the result and move to the next ip address.\n",
    "    For easier bit manipulation, we can convert an ip address to an integer whose binary representation represents the ip address.\n",
    "    '''\n",
    "    def ipToCIDR(self, ip: str, n: int) -> List[str]:\n",
    "        # convert an ip address to an integer whose binary representation represents the ip address\n",
    "        def ipToInt(ip: str) -> int:\n",
    "            res = 0\n",
    "            for part in ip.split('.'):\n",
    "                num = int(part)\n",
    "                res = res * 256 + num\n",
    "            return res\n",
    "\n",
    "        # convert an integer whose binary representation represents an ip address to the ip address\n",
    "        def intToIp(num: int) -> str:\n",
    "            res = []\n",
    "            for _ in range(4):\n",
    "                res.append(str(num % 256))\n",
    "                num //= 256\n",
    "            return '.'.join(res[::-1])\n",
    "\n",
    "        # count the number of trailing 0s in the binary representation of an integer\n",
    "        def countTrailingZeros(num: int) -> int:\n",
    "            if num == 0: # special case\n",
    "                return 32\n",
    "\n",
    "            res = 0\n",
    "            while num & 1 == 0:\n",
    "                res += 1\n",
    "                num >>= 1\n",
    "            return res\n",
    "\n",
    "        res = []\n",
    "        ipInt = ipToInt(ip)\n",
    "        while n > 0:\n",
    "            k = countTrailingZeros(ipInt)\n",
    "            while 2 ** k > n:\n",
    "                k -= 1\n",
    "            \n",
    "            # the current CIDR block masks the last k bits of ipInt and covers 2^k ip addresses\n",
    "            res.append(intToIp(ipInt) + '/' + str(32 - k))\n",
    "            n -= 2 ** k\n",
    "            ipInt += 2 ** k\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ipToCIDR(self, ip: str, n: int) -> List[str]:\n",
    "        def ip_to_int(ip):\n",
    "            ans = 0\n",
    "            for x in ip.split(\".\"):\n",
    "                ans = ans*256 + int(x)\n",
    "            return ans\n",
    "        \n",
    "        def int_to_ip(x):\n",
    "            return '.'.join(str((x >> i)%256) for i in (24,16,8,0))\n",
    "\n",
    "        start = ip_to_int(ip)\n",
    "        ans = []\n",
    "        while n:\n",
    "            #可用的位\n",
    "            if start == 0:\n",
    "                mask = n.bit_length() - 1\n",
    "            else:\n",
    "                mask = min((start&-start).bit_length() - 1,n.bit_length() - 1)\n",
    "            ans.append(int_to_ip(start) + '/' + str(32 - mask))\n",
    "            start += 1 << mask\n",
    "            n -= 1 << mask\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ipToCIDR(self, ip: str, n: int) -> List[str]:\n",
    "        \n",
    "        # 计算二进制ip地址字符串\n",
    "        # 末尾0个数\n",
    "        def calc_zp(s):\n",
    "            ans = 0\n",
    "            s = [\"0\"*(8-len(i))+i for i in [bin(int(i2))[2:] for i2 in s]]\n",
    "            for c in \"\".join(s)[::-1]:\n",
    "                if c!=\"0\":\n",
    "                    return ans\n",
    "                else:\n",
    "                    ans+=1\n",
    "            return ans\n",
    "              \n",
    "        ip = ip.split(\".\")\n",
    "        ans = []\n",
    "        \n",
    "        while n >0:\n",
    "            if int(ip[3]) < 255:\n",
    "                # 若目前ip末尾为奇数\n",
    "                # 则只有1个有效地址\n",
    "                # eg. xxxx.xxxx.xxxx.xxxx/32\n",
    "                if int(ip[3]) % 2 == 1:\n",
    "                    n = n -1\n",
    "                    ans.append(\".\".join(ip)+\"/32\")\n",
    "                    ip[3] = str(int(ip[3])+1)\n",
    "                # 若为偶数则有\n",
    "                # pow(2,（二进制）末尾0的个数) 个有效地址\n",
    "                else:\n",
    "                    zp = calc_zp(ip)\n",
    "                    while n-pow(2,zp)<0:\n",
    "                        zp -= 1\n",
    "                    n = n - pow(2,zp)\n",
    "                    ans.append(\".\".join(ip)+\"/\"+str(32-zp))\n",
    "                    ip[3] = str(int(ip[3])+pow(2,zp))\n",
    "            # 处理255进位情况\n",
    "            else:\n",
    "                for i in range(3,0,-1):\n",
    "                    ad = int(ip[i]) // 256\n",
    "                    ip[i] = str(int(ip[i]) % 256)\n",
    "                    ip[i-1] = str(int(ip[i-1])+ad)\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ipToCIDR(self, ip: str, n: int) -> List[str]:\n",
    "        def ip_to_bin(ip):\n",
    "            return \"\".join([\"{:08b}\".format(i) for i in map(int, ip.split(\".\"))])\n",
    "        def bin_to_ip(b):\n",
    "            return \".\".join([str(int(b[i:i+8],2)) for i in range(0, 32, 8)])\n",
    "        \n",
    "        ans = []\n",
    "        cur_ip = ip_to_bin(ip)\n",
    "        while n > 0:\n",
    "            last_one = 31\n",
    "            while last_one> -1 and cur_ip[last_one] != '1':\n",
    "                last_one -= 1\n",
    "            trailing_zero = 31 - last_one\n",
    "            while n - (2 ** trailing_zero) < 0:\n",
    "                trailing_zero -= 1\n",
    "            ans.append(f\"{bin_to_ip(cur_ip)}/{32 - trailing_zero}\")\n",
    "            n -= 2 ** trailing_zero\n",
    "            cur_ip = \"{:032b}\".format(int(cur_ip, 2) + 2 ** trailing_zero)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import log2\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def ipToCIDR(self, ip: str, n: int) -> List[str]:\r\n",
    "\r\n",
    "        def ip_to_int(ip):\r\n",
    "            num = 0\r\n",
    "            for x in ip.split('.'):\r\n",
    "                num *= 256\r\n",
    "                num += int(x)\r\n",
    "            return num\r\n",
    "\r\n",
    "        def int_to_ip(num):\r\n",
    "            lst = []\r\n",
    "            for _ in range(4):\r\n",
    "                num, r = divmod(num, 256)\r\n",
    "                lst.append(str(r))\r\n",
    "            return '.'.join(lst[::-1])\r\n",
    "\r\n",
    "        def low_bit(num):\r\n",
    "            return num & (-num)\r\n",
    "\r\n",
    "        res = []\r\n",
    "        num = ip_to_int(ip)\r\n",
    "        while n:\r\n",
    "            count = low_bit(num) or 1024\r\n",
    "            while count > n:\r\n",
    "                count >>= 1\r\n",
    "            res.append(int_to_ip(num) + '/' + str(32 - int(log2(count))))\r\n",
    "            num += count\r\n",
    "            n -= count\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ipToCIDR(self, ip: str, n: int) -> List[str]:\n",
    "        def ip_to_int(ip):\n",
    "            ans = 0\n",
    "            for x in ip.split('.'):\n",
    "                ans = 256 * ans + int(x)\n",
    "            # return ans\n",
    "            octets = [int(octet) for octet in ip.split('.')]\n",
    "            return (octets[0] << 24) + (octets[1] << 16) + (octets[2] << 8) + octets[3]\n",
    "        \n",
    "        def int_to_ip(x):\n",
    "            return '.'.join(str((x >> i) % 256) for i in (24, 16, 8, 0))\n",
    "        \n",
    "        start = ip_to_int(ip)\n",
    "        print(bin(start))\n",
    "        res = []\n",
    "        while n:\n",
    "            low_bit = (start & -start)\n",
    "            mask = max(33 - low_bit.bit_length(), 33 - n.bit_length())\n",
    "            if low_bit == 0:\n",
    "                mask = 33 - n.bit_length()\n",
    "            res.append(int_to_ip(start) + '/' + str(mask))\n",
    "            start += 1 << (32 - mask)\n",
    "            n -= 1 << (32 - mask)\n",
    "        return res\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
